import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;

//要求：滑动谜题，2*3矩阵里有12345和空6种格子，数字格子可以移到空格子位置，求最少步数移动，最终顺序12345空
//策略：保证移动过程中不出现重复，hashset记录中间结果，queue记录移动后的可能结果，times记录移动次数
public class SlidingPuzzle {

}
class SlidingPuzzleSolution {
    public int slidingPuzzle(int[][] board) {
        HashSet<Integer> set = new HashSet();
        Queue<Integer> queue = new LinkedList();
        int num = 0;
        for(int i=0;i<2;i++){
            for(int j=0;j<3;j++){
                num = num*10+board[i][j];
            }
        }
        set.add(num);
        queue.add(num);
        int count = queue.size();
        int times = 0;
        while(!queue.isEmpty()&&num!=123450){
            if(count==0) {
                count = queue.size();//记录移动数增加一次所有可能结果
                times++;
            }
            num = queue.poll();//顺序获得再移动一次后结果
            int tmp = num;
            int zerosite = 1;
            while(tmp%10!=0){
                tmp/=10;
                zerosite++;
            }
            //根据空格位置调整移动策略
            if(zerosite==1){
                tmp = swap(num,1,4);
                if(!set.contains(tmp)){
                    queue.add(tmp);
                    set.add(tmp);
                }
                tmp = swap(num,1,2);
                if(!set.contains(tmp)){
                    queue.add(tmp);
                    set.add(tmp);
                }
            }
            if(zerosite==3){
                tmp = swap(num,3,2);
                if(!set.contains(tmp)){
                    queue.add(tmp);
                    set.add(tmp);
                }
                tmp = swap(num,3,6);
                if(!set.contains(tmp)){
                    queue.add(tmp);
                    set.add(tmp);
                }
            }
            if(zerosite==4){
                tmp = swap(num,1,4);
                if(!set.contains(tmp)){
                    queue.add(tmp);
                    set.add(tmp);
                }
                tmp = swap(num,4,5);
                if(!set.contains(tmp)){
                    queue.add(tmp);
                    set.add(tmp);
                }
            }
            if(zerosite==6){
                tmp = swap(num,5,6);
                if(!set.contains(tmp)){
                    queue.add(tmp);
                    set.add(tmp);
                }
                tmp = swap(num,3,6);
                if(!set.contains(tmp)){
                    queue.add(tmp);
                    set.add(tmp);
                }
            }
            if(zerosite==2){
                tmp = swap(num,2,1);
                if(!set.contains(tmp)){
                    queue.add(tmp);
                    set.add(tmp);
                }
                tmp = swap(num,3,2);
                if(!set.contains(tmp)){
                    queue.add(tmp);
                    set.add(tmp);
                }
                tmp = swap(num,2,5);
                if(!set.contains(tmp)){
                    queue.add(tmp);
                    set.add(tmp);
                }
            }
            if(zerosite==5){
                tmp = swap(num,5,6);
                if(!set.contains(tmp)){
                    queue.add(tmp);
                    set.add(tmp);
                }
                tmp = swap(num,4,5);
                if(!set.contains(tmp)){
                    queue.add(tmp);
                    set.add(tmp);
                }
                tmp = swap(num,2,5);
                if(!set.contains(tmp)){
                    queue.add(tmp);
                    set.add(tmp);
                }
            }
            count--;
        }
        return num==123450?times:-1;
    }
    int swap(int num,int i,int j){
        int numi = (num/(int)Math.pow(10,i-1))%10;
        int pre = num/(int)Math.pow(10,i);
        int pos = num%(int)Math.pow(10,i-1);
        int numj = (num/(int)Math.pow(10,j-1))%10;
        int res = pre*(int)Math.pow(10,i)+pos+numj*(int)Math.pow(10,i-1);
        pre = res/(int)Math.pow(10,j);
        pos = res%(int)Math.pow(10,j-1);
        res = pre*(int)Math.pow(10,j)+pos+numi*(int)Math.pow(10,j-1);
        return res;
    }
}